The present invention relates to a system and method for retrieving site data, and is more particularly concerned with a system and method for retrieving location-qualified site data in response to a query.
The economic activity attributed to electronic commerce (xe2x80x9ce-commercexe2x80x9d) transactions is continuing to grow at a significant rate. Associated with this growth is an increased demand for functionality and infrastructure to aid the consumer purchasing process. Search engines, theme portals, and other Internet-based functions that generate or maintain directories of products and services are becoming an increasingly integral part of a consumer""s purchasing process. As consumers increase their use of Internet-based facilities, and firms increase their Internet exposure in response, the data repositories that support consumer-focused Internet-based directories are likely to experience significant growth.
Mobile commerce (xe2x80x9cm-commercexe2x80x9d) has emerged as a significant and growing segment of the field of e-commerce. M-commerce is increasingly the subject of application development activities and the object of escalating levels of business investment. In particular, transaction-enabling devices that serve the mobile consumer (xe2x80x9cm-commerce userxe2x80x9d) are becoming more readily available as the number of m-commerce users continues to grow. The adoption of technologies that involve the convergence of computing platforms for handheld computing devices, wireless web connectivity, and position-determining applications is increasing among m-commerce users. Consequently, m-commerce users may expect that data repositories underlying Internet-based product and service directories will be searchable by criteria that relates to the location of products, services, or organizations, in addition to being searchable by product, service, organizational, and other criteria. Thus, an m-commerce user""s location and the locations of business operations offering goods or services of interest to the user will become increasingly important in conducting and successfully concluding m-commerce transactions.
For example, the following questions typify some of the queries that may be posed by an m-commerce user. These questions require consideration of a user""s location and the location of business operations or other sites of interest:
(A) Where is the nearest cash machine?
(B) Are there any golf courses within walking distance?
(C) How close is the next gas station?
(D) What restaurants are within a block or two of my office?
Each question mentions a business operation or a site of interest that can be categorized by a site category relating to a product or service (e.g. cash machines, golf courses, gas stations, and restaurants). Each question also makes reference to a user-relative distance, that is, a distance between the location of the user and the location of the business operation or site (e.g. nearest, within walking distance, next, and within a block or two). Data relating to these business operations or sites of interest, including data that can be used to identify the location of a particular business operation or site, is typically stored in a site data repository. Rapid access to the data stored in the site data repository, especially for the purpose of resolving such queries by a user, is often an important factor in evaluating the level of service realized by a client platform of an m-commerce application.
According to a traditional approach, a query of the above nature is resolved by calculating the distance between a user""s location and the location of each and every business operation or site (of a specific site category, if specified) for which data is stored in the data repository. Once the distances between a user""s location and the location of each business operation or site are calculated, the query could be resolved using these calculated distances, by extracting only the data pertaining to business operations or sites which satisfied the query. However, this traditional approach may be time-consuming, particularly when there is a large number of business operations or sites for which data is stored in the data repository, since the location of all business operations or sites (of a specific site category, if specified) must be considered to resolve the query.
Some prior art methods attempt to resolve similar queries in a manner that may be more efficient than this traditional approach.
U.S. Pat. No. 6,108,650 discloses a method for performing an accelerated radius search for geographic entities near a starting point. In this method, density values corresponding to a geographic area are generated. These density values may be used to modify the search radius used in a first search, and in successive searches.
U.S. Pat. No. 6,021,406 discloses a method of searching a database to find objects in a given area and to find objects nearest to a location. In this method, a geographic plane is divided into a rectangular grid of squares. The squares are then numbered in order as dictated by a space filling curve, using spatial key numbers. The space filling curve allows for the representation of a two-dimensional plane using one-dimensional coordinates. Objects on the two-dimensional plane may span multiple squares. Given the property that consecutive spatial key numbers will identify neighboring squares, the use of the space filling curve allows the squares that an object spans to be identified in groups.
The present invention relates generally to a system and method for retrieving site data.
More specifically, the present invention relates to a system and method for retrieving site data stored in a site data repository, to linkcells, and to a system and method for generating linkcells for use in retrieving site data stored in a site data repository.
One aspect of the present invention relates to a linkcell for use in retrieving site data pertaining to one or more sites of a plurality of sites in a site set, wherein each site in the site set is located in a location space, wherein site data pertaining to sites in the site set is contained in a site data repository, and wherein the linkcell comprises: a cell perimeter that defines a cell space for the linkcell within the location space, wherein said cell perimeter comprises one or more cell boundary sections, and wherein each of said one or more cell boundary sections has a predefined coordinate interval associated therewith; a cell identifier; and a link to a data table; wherein at least one site of the site set is associated with the linkcell, and wherein site data pertaining to the at least one site is stored in the data table.
Another aspect of the present invention relates to a method of generating linkcells wherein the location of a site is defined by at least two coordinates, and wherein a cell identifier is derived from the at least two coordinates, the at least two coordinates defining the location of a site associated with the linkcell to which the cell identifier is assigned.
Another aspect of the present invention relates to a method of generating linkcells for use in retrieving site data pertaining to one or more sites of a plurality of sites in a site set, wherein each site in the site set is located in a location space, wherein site data pertaining to sites in the site set is contained in a site data repository, and wherein the method comprises the steps of: partitioning the location space into a plurality of cells; associating each site in the site set with one of the plurality of cells; defining a plurality of linkcells, wherein the plurality of linkcells is a subset of cells in the plurality of cells, and wherein each of the plurality of linkcells has at least one site associated therewith; assigning a cell identifier to each of the plurality of linkcells; linking a data table to each of the plurality of linkcells; and for each of the plurality of linkcells, storing site data pertaining to all sites associated therewith in the data table linked thereto.
Another aspect of the present invention relates to a method of retrieving site data pertaining to one or more sites of a plurality of sites in a site set, wherein each site in the site set is located in a location space, wherein site data pertaining to sites in the site set is contained in a site data repository, wherein a plurality of linkcells have been generated, wherein each linkcell comprises a cell space in the location space, wherein each linkcell has at least one site associated therewith, wherein each linkcell has been assigned a cell identifier, wherein each linkcell is linked to a data table, and wherein the method comprises the steps of: receiving a user-specified cell identifier as input; retrieving site data pertaining to at least one site associated with a linkcell to which the user-specified cell identifier has been assigned; and outputting site data retrieved to a user.
Another aspect of the present invention relates to a method of retrieving site data pertaining to one or more sites of a plurality of sites in a site set, wherein each site in the site set is located in a location space, wherein the location space is partitioned into cells, wherein site data pertaining to sites in the site set is contained in a site data repository, wherein site data pertaining to sites in the site set comprises a site identifier, wherein a plurality of linkcells have been generated, wherein each linkcell comprises a cell space in the location space, wherein each linkcell has at least one site associated therewith, wherein each linkcell has been assigned a cell identifier, wherein each linkcell is linked to a data table, and wherein the method comprises the steps of: receiving a user""s location; receiving a user request to retrieve site data pertaining to a specified number of sites closest to the user""s location; defining a core cell, wherein the core cell is in a searchable area defined in the location space; defining a cursor cell, wherein the cursor cell traverses a path of cells in the searchable area starting with the core cell until either the cursor cell has traversed all of the searchable area or the cursor cell has traversed one or more predefined layers of cells containing at least the specified number of sites, such that each time the cursor cell is positioned at a linkcell, sites associated with that linkcell are identified and for each identified site, the site identifier therefor and the distance between the user""s location and the identified site are stored in a result table; determining any additional linkcells in said searchable area that could have sites associated therewith that are closer to the user""s location than any of the first-identified pre-specified number of sites; identifying sites associated with the any additional linkcells; for each site associated with the any additional linkcells, storing the site identifier therefor and the distance between the user""s location and the site in a result table; determining the specified number of sites closest to the user""s location from the distances stored in the result table; retrieving site data pertaining to the specified number of sites closest to the user""s location; and outputting site data retrieved to a user.
Another aspect of the present invention relates to a method of retrieving site data pertaining to one or more sites of a plurality of sites in a site set, wherein each site in the site set is located in a location space, wherein the location space is partitioned into cells, wherein site data pertaining to sites in the site set is contained in a site data repository, wherein site data pertaining to sites in the site set comprises a site identifier, wherein a plurality of linkcells have been generated, wherein each linkcell comprises a cell space in the location space, wherein each linkcell has at least one site associated therewith, wherein each linkcell has been assigned a cell identifier, wherein each linkcell is linked to a data table, and wherein the method comprises the steps of: receiving a user""s location; receiving a user request to retrieve site data pertaining to sites located within a user-specified distance of the user""s location; defining a core cell, wherein the core cell is in a searchable area defined in the location space; defining a cursor cell, wherein the cursor cell traverses a path of cells in the searchable area starting with the core cell until either the cursor cell has traversed all of the searchable area or the cursor cell has traversed an area covering all points in the searchable area that are within the specified distance of the user""s location, such that each time when the cursor cell is positioned at a linkcell, sites associated with that linkcell are identified and for each identified site, the site identifier therefor and the distance between the user""s location and the identified site are stored in a result table; determining the sites within a user-specified distance to the user""s location from the distances stored in the result table; retrieving site data pertaining to the sites within a user-specified distance to the user""s location; and outputting site data retrieved to a user.
Another aspect of the invention relates to a system for retrieving site data pertaining to one or more sites of a plurality of sites in a site set, wherein each site in the site set is located in a location space, wherein the location space is partitioned into cells, wherein site data pertaining to sites in the site set comprises a site identifier, the system comprising: a site data repository, wherein site data pertaining to sites in the site set is contained in the site data repository; a storage means for storing data tables; a user interface; and one or more processing modules connected to the site data repository, the storage means, and the user interface, wherein the processing modules are programmed to perform the steps of a method of an embodiment of the present invention.
The present invention is directed to the use of linkcells in retrieving site data pertaining to one or more sites from a site data repository. The linkcells facilitate the resolution of several types of queries, including queries to determine a specified number of closest sites (of one or more specific site categories, if desired) to a user""s location, and queries to determine sites (of one or more specific site categories, if desired) located within a specified distance of the user""s location, for example.
In an embodiment of the present invention, a linkcell is assigned a name derived from the coordinates of sites associated with the linkcell. Advantageously, in this embodiment, the coordinates of any site to which site data stored in the site data repository pertains provide all the information needed to uniquely identify the linkcell with which that site is associated. The name assigned to a linkcell also provides a unique reference to a section of a location space containing sites for which site data is stored in the site data repository.
Advantageously, these linkcells provide a means for resolving some queries more efficiently than a traditional approach, at least for some sizes of site data repositories.